package com.klun.project.common.constans.leetcode;

//一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
//'A' -> "1"
//'B' -> "2"
//...
//'Z' -> "26"
//
// 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
// "AAJF" ，将消息分组为 (1 1 10 6)
// "KJF" ，将消息分组为 (11 10 6)
// 注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
// 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
// 题目数据保证答案肯定是一个 32 位 的整数。
//
// 示例 1：
//输入：s = "12"
//输出：2
//解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
//
// 示例 2：
//输入：s = "226"
//输出：3
//解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
//
// 示例 3：
//输入：s = "0"
//输出：0
//解释：没有字符映射到以 0 开头的数字。
//含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
//由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
//
public class Solution91 {

	public int numDecodings(String s) {
		char[] cs = s.toCharArray();
		int len = s.length();
		if (len == 1) {
			if (cs[0] - 48 == 0) return 0;
			return 1;
		}
		int[] dp = new int[len];
		int temp = cs[0] - 48;
		dp[0] = temp > 0 ? 1 : 0;
		for (int i = 1; i < len; i++) {
			int c = cs[i] - 48;
			int count = 1;
			if (c == 0) count = 0;
			if (c + temp * 10 <= 26 && temp != 0) {
				dp[i] = count + dp[i - 1];
			} else {
				dp[i] = dp[i - 1];
			}
			temp = c;
		}
		return dp[len - 1];
	}
	public int numDecodings1(String s) {
		int n = s.length();
		int[] f = new int[n + 1];
		f[0] = 1;
		for (int i = 1; i <= n; ++i) {
			if (s.charAt(i - 1) != '0') {
				f[i] += f[i - 1];
			}
			if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
				f[i] += f[i - 2];
			}
		}
		return f[n];
	}

	public static void main(String[] args) {
		Solution91 solution = new Solution91();
//		obstacleGrid = [[0,0,0],[0,1,0],[0,0,0],[0,0,0]];
//		int[][] ints = ParseUtils.StringToArrayInt("[[1,3,1],[1,5,1],[4,2,1]]");
		System.out.println(solution.numDecodings1("21001"));
	}

}
